package com.alghtroms;

public class LCS {

	public int lcs(String str1,String str2,int m,int n){
		if(m==0||n==0){
			return 0;
		}
		
		if(str1.charAt(m-1)==str2.charAt(n-1)){
			return lcs(str1,str2,m-1,n-1)+1;
		}else{
		   return Math.max(lcs(str1,str2,m-1,n), lcs(str1,str2,m,n-1));	
		}
	}
	
	public static void main(String[] args) {
		LCS l=new LCS();
		String X = "ABCBDAB";  
	    String Y = "BDCABA";
	    System.out.println(l.lcs(X, Y, X.length(),Y.length()));
	}
}
